Invalid transactions [Sliding Window, Line Sweep]

Time: O(NLogN); Space: O(N); medium

A transaction is possibly invalid if: * the amount exceeds $1000, or; * if it occurs within (and including) 60 minutes of another transaction with the same name in a different city.

Each transaction string transactions[i] consists of comma separated values representing the name, time (in minutes), amount, and city of the transaction.

Given a list of transactions, return a list of transactions that are possibly invalid. You may return the answer in any order.

Example 1:

Input: transactions =

["alice, 20, 800, mtv",
 "alice, 50, 100, beijing"
]

Output:

["alice, 20, 800, mtv",
 "alice, 50, 100, beijing"]

Explanation:

  • The first transaction is invalid because the second transaction occurs within a difference of 60 minutes, have the same name and is in a different city.

  • Similarly the second one is invalid too.

Example 2:

Input: transactions =

["alice, 20, 800, mtv",
 "alice, 50, 1200, mtv"]

Output:

["alice, 50, 1200, mtv"]

Example 3:

Input: transactions =

["alice, 20, 800, mtv",
 "bob, 50, 1200, mtv"]

Output:

["bob, 50, 1200, mtv"]

Notes:

  • len(transactions) <= 1000

  • Each transactions[i] takes the form “{name},{time},{amount},{city}”

  • Each {name} and {city} consist of lowercase English letters, and have lengths between 1 and 10.

  • Each {time} consist of digits, and represent an integer between 0 and 1000.

  • Each {amount} consist of digits, and represent an integer between 0 and 2000.

[5]:

import collections

class Solution1(object):
    def invalidTransactions(self, transactions):
        AMOUNT, MINUTES = 1000, 60

        trans = list(map(lambda x: (x[0], int(x[1]), int(x[2]), x[3]),
                    (transaction.split(',') for transaction in transactions)))
        trans.sort(key=lambda t: t[1])
        trans_indexes = collections.defaultdict(list)

        for i, t in enumerate(trans):
            trans_indexes[t[0]].append(i)

        result = []
        for name, indexes in trans_indexes.items():
            left, right = 0, 0
            for i, t_index in enumerate(indexes):
                t = trans[t_index]
                if (t[2] > AMOUNT):
                    result.append("{},{},{},{}".format(*t))
                    continue

                while left+1 < len(indexes) and trans[indexes[left]][1] < t[1]-MINUTES:
                    left += 1

                while right+1 < len(indexes) and trans[indexes[right+1]][1] <= t[1]+MINUTES:
                    right += 1

                for i in range(left, right+1):
                    if trans[indexes[i]][3] != t[3]:
                        result.append("{},{},{},{}".format(*t))
                        break
        return result

[11]:

s = Solution1()
transactions = ["alice, 20, 800, mtv", "alice, 50, 100, beijing"]
assert s.invalidTransactions(transactions) == ['alice,20,800, mtv', 'alice,50,100, beijing']
transactions = ["alice, 20, 800, mtv", "alice, 50, 1200, mtv"]
assert s.invalidTransactions(transactions) == ['alice,50,1200, mtv']
transactions = ["alice, 20, 800, mtv", "bob, 50, 1200, mtv"]
assert s.invalidTransactions(transactions) == ['bob,50,1200, mtv']